package hashstudy;

public class HashMap<K,V> implements Map<K,V>{

    private Entry<K,V> table[] = null;

    int size = 0;

    public HashMap() {
        this.table = new Entry[16];
    }

    /***
     * 通过key hash算法 算出hash值 hash值取模
     * 获取到index下标
     * 判断当前对象时都为空 如空 直接存储
     * 非空，发生了冲突，就用next链表
     * 返回当前节点对象
     * @param k
     * @param v
     * @return
     */
    @Override
    public V put(K k, V v) {
        int index = hash(k);
        Entry<K,V> entry = table[index];
        if(null == entry){
            //直接存
            table[index] = new Entry<>(k,v,index,null);
            size ++;
        }else{
            //hash冲突
            table[index] = new Entry<>(k,v,index,entry);
        }
        return table[index].getValue();
    }

    private int hash(K k) {
        int index = k.hashCode()%16;
        //如果hash值为负数，就负负得正
        return index>=0?index:-index;
    }

    /***
     * 仍然是获取hash值，通过hash值找到索引
     * 如果该位置为空，则返回空
     * 如果该位置的hash值相同，则返回这个值
     * 如果该位置的hash值不同，那么向下遍历next节点
     * @param k
     * @return
     */
    @Override
    public V get(K k) {
        if(size == 0)
            return null;
        int index = hash(k);
        //idea补全变量   ctrl+alt+v
        //Entry<K, V> entry = table[index];
        Entry<K,V> entry = findValue(table[index],k);
        return entry==null?null:entry.getValue();
    }

    /***
     * 将查询
     * @param entry
     * @param k 查询key
     * @return
     */
    private Entry<K,V> findValue(Entry<K,V> entry, K k) {
        if(k.equals(entry.getKey()) || k == entry.getKey()){
            return entry;
        }else{
            if(entry.next != null){
                return findValue(entry.next,k);
            }
        }
        return null;
    }

    @Override
    public int size() {
        return size;
    }

    class Entry<K,V> implements Map.Entry<K,V>{

        K k;
        V v;
        int hash;
        Entry<K,V> next;

        public Entry(K k, V v, int hash, Entry<K, V> next) {
            this.k = k;
            this.v = v;
            this.hash = hash;
            this.next = next;
        }

        @Override
        public K getKey() {
            return k;
        }

        @Override
        public V getValue() {
            return v;
        }
    }
}
